Consulta de Guías Docentes



Academic Year/course: 2022/23

625 - Bachelor's Degree in Industrial Processes' Data Engineering

29506 - Graphs and Network Optimization


Syllabus Information

Academic Year:
2022/23
Subject:
29506 - Graphs and Network Optimization
Faculty / School:
175 - Escuela Universitaria Politécnica de La Almunia
Degree:
625 - Bachelor's Degree in Industrial Processes' Data Engineering
ECTS:
6.0
Year:
1
Semester:
Second semester
Subject Type:
Basic Education
Module:
---

1. General information

1.1. Aims of the course

This course is an introduction to Graph Theory and Combinatorial Optimization and its practical use. The student is introduced to the use of computer tools with in order to cover practical aspects of the application of graphs to combinatorial optimization problems. The ultimate goal is that students integrate basic knowledge of the course in all kinds of topics related with their future professional life.

These approaches and objectives are in line with the following Sustainable Development Goals (SDGs) of the United Nations 2030 Agenda (https://www.un.org/sustainabledevelopment/es/), in such a way that the acquisition of the course learning outcomes provides training and competence to contribute to their achievement to some degree:

  • Goal 4: Quality Education
    • 4.4 By 2030, substantially increase the number of youth and adults who have relevant skills, including technical and vocational skills, for employment, decent jobs and entrepreneurship
    • 4.5 By 2030, eliminate gender disparities in education and ensure equal access to all levels of education and vocational training for the vulnerable, including persons with disabilities, indigenous peoples and children in vulnerable situations
  • Goal 9: Build resilient infrastructure, promote sustainable industrialization and foster innovation
    • 9.5 Enhance scientific research, upgrade the technological capabilities of industrial sectors in all countries, in particular developing countries, including, by 2030, encouraging innovation and substantially increasing the number of research and development workers per 1 million people and public and private research and development spending
  • Goal 16: Promote just, peaceful and inclusive societies
    • 16.5 Substantially reduce corruption and bribery in all their forms

1.2. Context and importance of this course in the degree

This course is compulsory and belongs to the basic education module. It is taken during the second semester of the first year of the Bachelor's Degree in Data Engineering in Industry Processes.

Moreover, Graph Theory and Combinatorial Optimization provides skills in tools relevant to different subsequent courses with contents such as data structures, programming, electronics, database management, optimization, etc.

Network optimization techniques constitute an essential tool to address the treatment of data acquisition and processing systems.

Because of these reasons, Graphs and Network Optimization is a basic tool in a Data Engineer's education.

1.3. Recommendations to take this course

The subject is self-contained with very little mathematical prerequisites. It is advisable that the student is familiar with the use of symbolic and numerical computer programs, although the programs that we will use are treated from scratch.

2. Learning goals

2.1. Competences

In passing this subject, the student will be competent in:

  1. BASIC COMPETENCES
    CB2   That students know how to apply their knowledge to their job or vocation in a professional way and possess the competencies that are often demonstrated by means of the elaboration and defense of arguments and the problem solving within their study area
    CB4   That students can transmit information, ideas, problems and solutions to a specialized as well as non-specialized audience
    CB5   That the students have developed those learning skills necessary to undertake subsequent studies with a high degree of autonomy
  2. GENERAL COMPETENCES
    CG3   Knowledge of basic scientific and technical subjects aimed at data acquisition, data management and data processing in Engineering.
    CG6   Ability to implement solutions derived from data analysis that optimize industrial production processes.
  3. TRANSVERSAL COMPETENCES
    CT03   Search, select and manage information and knowledge responsibly.
    CT04   Develop critical thinking and reasoning.
    CT05   Communication of results effectively.
    CT07   Analyze and solve problems autonomously, adapt to unforeseen situations and make decisions.
  4. SPECIFIC COMPETENCES
    CE04   Ability to solve mathematical problems that may arise in Engineering. Ability to apply knowledge about: Linear Algebra; Graph Theory; Differential and Integral Calculus, Differential Equations, Numerical Methods and Probability Calculus.

2.2. Learning goals

The student, in order to pass this subject, will have to achieve the following goals…

  • Learning the necessary basic knowledge to solve mathematical problems that can be posed in Linear Algebra; Graph Theory; Differential and Integral Calculus, Numerical Methods and Optimization.
  • Identifying the fundamental elements of a graph, as well as the problems associated with network optimization.
  • Possessing scientific-mathematical thinking skills, which allow them to ask and answer certain mathematical questions.
  • Having the ability to handle mathematical language; in particular, symbolic and formal language.

2.3. Importance of learning goals

In the subject of Graphs and Network Optimization, the main topic are the basic principles of network search and optimization algorithms which lie at the heart of data acquisition and processing. The students develop competencies to tackle real problems and learn to recognize and manage different problems of optimization that actually appear as contextualized versions of the problems studied on abstract graphs.

3. Assessment (1st and 2nd call)

3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

Students must show that they have achieved the expected learning outcomes through the following assessment activities:

  • Continuous assessment system:

    • Written tests: Throughout the semester there will be two written tests on theoretical and practical aspects on the subject::

      Written test 1:   It will be done on week 8. It will cover Graph Theory topics. Its weight in the final grade will be 40 %.
      Written test 2:   It will be done on week 14. It will cover Network Optimization. Its weight in the final grade will be 40 %.

      These tests will assess:

      • The understanding of mathematical and statistical topics used in problem solving.
      • The correct use of strategies and appropriate procedures towards its resolution.
      • Clear and detailed explanations.
      • The correct use of terminology and notation.
      • Orderly, clear and organized exhibition.

      In order to opt for the continuous assessment modality, it is necessary to attend at least 80% of the classroom activities of the subject.

    • Participatory tests: Throughout the course, the student will carry out 4 participatory tests valued at 5% of the final grade. They will consist of carrying out practical exercises.

      These tests will assess:

      • The understanding of mathematical and statistical topics used in problem solving.
      • The correct use of strategies and appropriate procedures towards its resolution.
      • Clear and detailed explanations.
      • The correct use of terminology and notation.
      • Orderly, clear and organized exhibition.

  • Global assessment

    Students who have not passed the subject with the continuous assessment system must take a compulsory written test in official calls equivalent to the written tests described in point 1, whose weight in the final grade will be 100%. The evaluation criteria will be those described in the previous sections.

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The learning process designed for this subject is based on the following:

The proposed methodology tries to promote continued work of the student and focuses on practical aspects of Graph Theory and Combinatorial Optimization: working with real situations.

In order to achieve this goal, all practical classes will be carried out in the computer room. The use of computer tools will be carried out in a continued manner.  Theoretical explanations of the concepts of the subject will be reinforced with examples or practical cases analyzed with the help of the computer.

The approach, methodology and assessment of this guide are intended to be the same for any teaching scenarios. They will be adapted to the social-health situation at any particular time, as well as to the instructions given by the authorities concerned.

4.2. Learning tasks

The programme offered to the student to help them achieve their target results is made up of the following activities…

The subject is articulated with 4 weekly hours of face-to-face class during the 15 weeks which the semester lasts. All lessons are taught in the computer room, where the considered theoretical concepts are reinforced with practical work by using numerical and symbolic computing programs.

4.3. Syllabus

Subject syllabus:

  1. Graphs: Basic concepts
  2. Planar graphs
  3. Graph colouring
  4. Matching
  5. Trees
  6. Matrix graph analysis
  7. Optimization problems in weighted graphs
  8. Network flows
  9. Algorithmic complexity
  10. Traveling Salesperson Problem
  11. Further combinatorial optimizacion problems

4.4. Course planning and calendar

The dates of the final exams will be those that are officially published at https://eupla.unizar.es/asuntos-academicos/examenes.

Week Theme Topic Tests Weight Content
1 1 Graphs: Basic Concepts      
2          
3 2 Planar Graphs      
4 3 Graph Colouring 1st test 5 Basics, planarity, colouring
5 4 Matching      
6 5 Trees 2nd test 5 Matching, Trees
7 6 Graph Matrix Analysis 1st exam 40 Graph Theory
8 7 Optimization Problems      
9 8 Network Flows      
10     3rd test 5 Optimization, Flows
11 9 Algorithmic Complexity      
12          
13 10 Traveling Salesperson Problem 4th test 5 Traveling Salesperson Problem
14 11 Further Problems      
15     2nd exam 40 Combinatorial optimization

 

4.5. Bibliography and recommended resources

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=29506


Curso Académico: 2022/23

625 - Graduado en Ingeniería de Datos en Procesos Industriales

29506 - Grafos y optimización en redes


Información del Plan Docente

Año académico:
2022/23
Asignatura:
29506 - Grafos y optimización en redes
Centro académico:
175 - Escuela Universitaria Politécnica de La Almunia
Titulación:
625 - Graduado en Ingeniería de Datos en Procesos Industriales
Créditos:
6.0
Curso:
1
Periodo de impartición:
Segundo semestre
Clase de asignatura:
Formación básica
Materia:
Materia básica de grado

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

En esta asignatura se introduce al alumno en los fundamentos de la teoría de Grafos y la Optimización Combinatoria y su uso a nivel práctico. Se le inicia en el uso de herramientas de tipo informático, y mediante ellas se cubren aspectos prácticos del uso de la teoría de Grafos y su aplicación a problemas de optimización en redes. El objetivo final es que el o la estudiante integre los conocimientos básicos de esta asignatura en todo tipo de materias relacionadas con su futura práctica profesional.

Estos planteamientos y objetivos están alineados con los siguientes Objetivos de Desarrollo Sostenible (ODS) de la Agenda 2030 de Naciones Unidas (https://www.un.org/sustainabledevelopment/es/), de tal manera que la adquisición de los resultados de aprendizaje de la asignatura proporciona capacitación y competencia para contribuir en cierta medida a su logro:

  • Objetivo 4: Garantizar una educación inclusiva, equitativa y de calidad y promover oportunidades de aprendizaje durante toda la vida para todos
    • Meta 4.4 De aquí a 2030, aumentar considerablemente el número de jóvenes y adultos que tienen las competencias necesarias, en particular técnicas y profesionales, para acceder al empleo, el trabajo decente y el emprendimiento
    • Meta 4.5 De aquí a 2030, eliminar las disparidades de género en la educación y asegurar el acceso igualitario a todos los niveles de la enseñanza y la formación profesional para las personas vulnerables, incluidas las personas con discapacidad, los pueblos indígenas y los niños en situaciones de vulnerabilidad.
  • Objetivo 9: Construir infraestructuras resilientes, promover la industrialización sostenible y fomentar la innovación
    • Meta 9.5 Aumentar la investigación científica y mejorar la capacidad tecnológica de los sectores industriales de todos los países, en particular los países en desarrollo, entre otras cosas fomentando la innovación y aumentando considerablemente, de aquí a 2030, el número de personas que trabajan en investigación y desarrollo por millón de habitantes y los gastos de los sectores público y privado en investigación y desarrollo
  • Objetivo 16: Promover sociedades justas, pacíficas e inclusivas
    • Meta 16.5 Reducir considerablemente la corrupción y el soborno en todas sus formas.

1.2. Contexto y sentido de la asignatura en la titulación

La asignatura es obligatoria y forma parte de la formación básica. Se imparte en el segundo semestre del primer curso del plan de estudios del Grado de Ingeniería de Datos en Procesos Industriales.

Además, la teoría de Grafos proporciona destrezas en herramientas que serán de utilidad en distintas asignaturas de cursos posteriores con contenidos en estructuras de datos, programación, electrónica, bases de datos, optimización, etc.

Las técnicas de optimización en redes constituyen una herramienta imprescindible para abordar el tratamiento de los sistemas de adquisición y procesado de datos.

Por estas causas, la teoría de Grafos es una herramienta básica en la formación de un ingeniero de datos en procesos industriales.

1.3. Recomendaciones para cursar la asignatura

La asignatura es autocontenida con prácticamente ningún requisito previo de conocimiento matemático. Es recomendable que el estudiante esté familiarizado con el uso de programas de cálculo simbólico y numérico, si bien los programas que usaremos se tratan desde cero.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para…

  1. COMPETENCIAS BÁSICAS
    CB2   Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio
    CB4   Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado
    CB5   Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía
  2. COMPETENCIAS GENERALES
    CG3   Conocimiento de materias básicas científicas y técnicas que capaciten para la adquisición, gestión y tratamiento de datos en la Ingeniería.
    CG6   Capacidad para implementar soluciones derivadas del análisis de datos que optimicen los procesos de producción en la industria.
  3. COMPETENCIAS TRANSVERSALES
    CT03   Buscar, seleccionar y gestionar de manera responsable la información y el conocimiento.
    CT04   Desarrollar un pensamiento y un razonamiento crítico
    CT05   Comunicación de resultados de manera efectiva.
    CT07   Analizar y solucionar problemas de forma autónoma, adaptarse a situaciones imprevistas y tomar decisiones.
  4. COMPETENCIAS ESPECÍFICAS
    CE04   Capacidad para la resolución de los problemas matemáticos que puedan plantearse en la ingeniería. Aptitud para aplicar los conocimientos sobre: álgebra lineal; teoría de grafos; cálculo diferencial e integral, ecuaciones diferenciales, métodos numéricos y cálculo de probabilidades.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados…

  • Aprender las bases necesarias para resolver problemas matemáticos que pueden plantearse en Álgebra Lineal; Teoría de grafos; Cálculo Diferencial e Integral, Métodos Numéricos y Optimización.
  • Identificar los elementos fundamentales de un grafo, así como los problemas asociados a optimización en redes.
  • Poseer habilidades propias del pensamiento científico-matemático, que le permiten preguntar y responder a determinadas cuestiones matemáticas.
  • Tener destreza para manejar el lenguaje matemático; en particular, el lenguaje simbólico y formal.

2.3. Importancia de los resultados de aprendizaje

En la asignatura de Grafos y optimización en redes se enseñan los principios básicos sobre los que se basan los algoritmos de optimización y búsqueda en redes que están en la base de la acquisición y procesamiento de datos. Los estudiantes desarrollan competencias para abordar problemas reales y aprenden a reconocer y manejar diferentes problemas de optimización que aparecen en la realidad como versiones contextualizadas de los problemas estudiados sobre grafos abstractos.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluación:

  • Sistema de evaluación continua:

    • Pruebas escritas: A lo largo del curso se realizarán dos pruebas escritas. Versarán sobre aspectos teóricos y/o prácticos de la asignatura:

      Prueba escrita 1:   Se realizará la semana 8 y versará sobre Teoría de Grafos. Su peso en la nota final será de un 40 %.
      Prueba escrita 2:   Se realizará la semana 15 y versará sobre Optimización en Redes. Su peso en la nota final será de un 40%.

      En estas pruebas se evaluará:

      • El entendimiento de los conceptos matemáticos usados para resolver los problemas.
      • El uso de estrategias y procedimientos en su resolución.
      • Explicaciones claras y detalladas.
      • Uso correcto de la terminología y notación.
      • Exposición ordenada, clara y organizada.

      Para poder optar por la modalidad de evaluación continua, es necesario asistir al menos a un 80% de las actividades presenciales de la asignatura.

    • Controles participativos: A lo largo del curso el alumno realizará 4 controles de tipo participativo valorados en un 5% de la nota final, que consistirán en la realización de ejercicios de tipo práctico.

      En estas pruebas se evaluará:

      • El entendimiento de los conceptos matemáticos usados para resolver los problemas.
      • El uso de estrategias y procedimientos en su resolución.
      • Explicaciones claras y detalladas.
      • Uso correcto de la terminología y notación.
      • Exposición ordenada, clara y organizada.

  • Evaluación global

    Los alumnos que no hayan superado la asignatura con el sistema de calificación continuada, deberán realizar en las convocatorias oficiales una prueba escrita de carácter obligatorio equivalente a las pruebas escritas descritas en el punto 1, cuyo peso en la nota final será del 100%.

    Los criterios de evaluación serán los descritos en los apartados anteriores.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

La metodología que se propone trata de fomentar el trabajo continuado del estudiante y se centra en los aspectos más prácticos de la teoría de Grafos y la Optimización Combinatoria: el trabajo con situaciones reales.

Con el fin de conseguir este objetivo todas las clases prácticas se realizarán en el aula de informática. El uso de herramientas de tipo informático se llevará a cabo de forma continuada. Las explicaciones teóricas de los conceptos de la asignatura serán reforzadas con ejemplos o casos prácticos analizados con la ayuda del ordenador.

El planteamiento, metodología y evaluación de esta guía está preparado para ser el mismo en cualquier escenario de docencia. Se ajustarán a las condiciones socio-sanitarias de cada momento, así como a las indicaciones dadas por las autoridades competentes.

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades…

La asignatura se articula con 4 horas de clase presencial a la semana durante las 15 semanas que dura el cuatrimestre. Todas las horas se imparten en el aula de informática, donde se consideran conceptos teóricos que son reforzados con el trabajo práctico mediante el uso de programas de cálculo numérico y simbólico.

4.3. Programa

El programa de la asignatura:

  1. Grafos: Conceptos básicos
  2. Grafos planos
  3. Coloración de grafos
  4. Emparejamiento
  5. Árboles
  6. Análisis matricial de grafos
  7. Problemas de optimización en grafos ponderados
  8. Flujo en redes
  9. Complejidad algorítmica
  10. El problema del viajante
  11. Otros problemas de optimización combinatoria

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Las fechas de los exámenes finales se publicarán oficialmente en https://eupla.unizar.es/asuntos-academicos/examenes.

Los contenidos de la asignatura, los hitos evaluatorios y su distribución por semanas será aproximadamente como sigue:

Semana Tema Contenidos Hitos evaluatorios Pesos Contenido
1 1 Grafos: conceptos básicos      
2          
3 2 Grafos planos      
4 3 Coloración de grafos 1er control 5 Básicos, planos, coloración
5 4 Emparejamiento      
6 5 Árboles 2º control 5 Emparejamiento, árboles
7 6 Análisis matricial de grafos 1ª prueba escrita 40 Grafos
8 7 Problemas de optimización      
9 8 Flujo en redes      
10     3er control 5 Optimización, Flujos
11 9 Complejidad algorítmica      
12          
13 10 El problema del viajante 4º control 5 Problema del viajante
14 11 Otros problemas      
15     2ª prueba escrita 40 Optimización combinatoria

4.5. Bibliografía y recursos recomendados